package offer;

import java.util.LinkedList;

public class offer_0059_2 {
    class MaxQueue {
        LinkedList<int[]> max;
        LinkedList<int[]> queue;
        int current;
        public MaxQueue() {
            max=new LinkedList<>();
            queue=new LinkedList<>();
            current=0;
        }

        public int max_value() {
            if(max.isEmpty()) return -1;
            return max.getFirst()[0];
        }

        public void push_back(int value) {
            int[] tep={value,current};
            current++;
            queue.add(tep);
            while(!max.isEmpty()&&max.getLast()[0]<value){
                max.removeLast();
            }
            max.add(tep);
        }

        public int pop_front() {
            if(queue.isEmpty()) return -1;
            int[] tep=queue.removeFirst();
            if(tep[1]==max.getFirst()[1]) max.removeFirst();
            return tep[0];
        }
    }
}
